Field
The present systems, methods and articles generally relate to solving computational problems and particularly relate to solving discrete optimization problems and/or constraint satisfaction problems by reverse or undirected execution of their corresponding logic circuit representations.
Discrete Optimization
In mathematics and computer science, an optimization problem is one in which an optimal value of at least one parameter is sought. Typically, the parameter in question is defined by an objective function which comprises at least one variable. The optimal value of the parameter is then achieved by determining the value(s) of the at least one variable that maximize or minimize the objective function.
Discrete optimization is simply a special-case of optimization for which the variables used in the objective function are restricted to assume only discrete values. For example, the variables in the objective function may be restricted to all or a subset of the integers.
Constraint Satisfaction
The maximization or minimization of the objective function in an optimization problem (discrete or otherwise) is typically subject to a set of constraints, where a valid result may be required to satisfy all, or at least a subset, of the constraints. In some applications, simply finding a solution that satisfies all, or a subset, of the constraints may be all that is desired (i.e., there may be no additional objective function requiring maximization or minimization). Such problems are known as “constraint satisfaction problems” and may be viewed as a class of optimization problems in which the objective function is a measure of how well the constraints are (or are not) satisfied. Thus, throughout the remainder of this specification, the term “optimization problem” is used to encompass all forms of optimization problems, including constraint satisfaction problems.
Quadratic Unconstrained Binary Optimization Problems
A quadratic unconstrained binary optimization (“QUBO”) problem is a form of discrete optimization problem that involves finding a set of N binary variables {xi} that minimizes an objective function of the form:
      E    ⁡          (                        x          1                ,        …        ⁢                                  ,                  x          N                    )        =            ∑              i        ≤        j            N        ⁢                  Q        ij            ⁢              x        i            ⁢              x        j            where Q is typically a real-valued upper triangular matrix that is characteristic of the particular problem instance being studied. QUBO problems are known in the art and applications arise in many different fields, for example machine learning, pattern matching, economics and finance, and statistical mechanics, to name a few.Logic Circuits
For any problem that can be solved, a solution may be reached by following a prescribed set of steps. In many cases, the prescribed set of steps may be designed to include a set of logical steps called “logical operations.” Logical operations are the fundamental steps that are typically implemented in digital electronics and most classical computer algorithms.
For many computational problems, a sequence of steps that leads to a solution can be described by a logic circuit representation. A logic circuit representation includes at least one logical input that is transformed to at least one logical output through at least one logical operation. A logic circuit representation may include any number of logical operations arranged either in series or in parallel (or a combination of series and parallel operations), where each logical operation has a corresponding set of at least one intermediate logical input and at least one intermediate logical output. Throughout this specification and the appended claims, the terms “intermediate logical input” and “intermediate logical output” are often used. Unless the specific context requires otherwise, the term “intermediate” here is intended to denote an input to/output from an individual logic gate which is an intermediate input/output with respect to the overall logic circuit. However, those of skill in the art will appreciate that a logical input to a logic circuit may correspond to an intermediate logical input to a particular logic gate, and similarly a logical output from a logic circuit may correspond to an intermediate logical output from a particular logic gate. For a first logical operation arranged in series with a second logical operation, at least one intermediate logical output from the first logical operation may correspond to at least one intermediate logical input to the second logical operation.
Each logical operation in a logic circuit is represented by a logic gate, for example, the NAND gate or the XOR gate, or a combination of logic gates. A logical operation may include any number of logic gates arranged either in series or in parallel (or a combination of series and parallel gates), where each logic gate has a corresponding set of at least one intermediate logical input and at least one intermediate logical output. For a first logic gate arranged in series with a second logic gate, at least one intermediate logical output from the first logic gate may correspond to at least one intermediate logical input to the second logic gate. The complete logic circuit representation of a computational problem may include any number of intermediate logical operations which themselves may include any number of intermediate logic gates. Furthermore, the at least one logical input to the logic circuit representation may traverse any number of intermediate logical inputs and intermediate logical outputs in being transformed to the at least one logical output from the logic circuit representation. Unless the specific context requires otherwise, throughout the remainder of this specification and the appended claims the terms “logical input” and “logical output” are used to generally describe any inputs and outputs in a logic circuit representation, including intermediate inputs and outputs.
In some implementations, one or more logical inputs may produce a plurality of logical outputs. For example, if the circuit, an operation, or a gate produces an N-bit number as the result, then N logical outputs may be required to represent this number. Alternatively, one or more logical inputs may produce a single logical output. For example, if the circuit, an operation, or a gate produces TRUE or FALSE as the result, then only one logical output may be required to convey this information. A circuit that produces TRUE or FALSE as the result embodies “Boolean logic” and is sometimes referred to as a “Boolean circuit.” Boolean circuits are commonly used to represent NP-complete constraint satisfaction problems.
Quantum Processor
A computer processor may take the form of an analog processor, for instance a quantum processor such as a superconducting quantum processor. A superconducting quantum processor may include a number of qubits and associated local bias devices, for instance two or more superconducting qubits. Further detail and embodiments of exemplary quantum processors that may be used in conjunction with the present systems, methods, and apparatus are described in US Patent Publication No. 2006-0225165 (now U.S. Pat. No. 7,533,068), US Patent Publication 2008-0176750, U.S. patent application Ser. No. 12/266,378 published as U.S. Patent Publication 2009-0121215, and PCT Patent Application Serial No. PCT/US09/37984 published as PCT Patent Publication 2009-120638.
Adiabatic Quantum Computation
Adiabatic quantum computation typically involves evolving a system from a known initial Hamiltonian (the Hamiltonian being an operator whose eigenvalues are the allowed energies of the system) to a final Hamiltonian by gradually changing the Hamiltonian. A simple example of an adiabatic evolution is:He=(1−s)Hi+sHf 
where Hi is the initial Hamiltonian, Hf is the final Hamiltonian, He is the evolution or instantaneous Hamiltonian, and s is an evolution coefficient which controls the rate of evolution. As the system evolves, the coefficient s goes from 0 to 1 such that at the beginning (i.e., s=0) the evolution Hamiltonian He is equal to the initial Hamiltonian Hi and at the end (i.e., s=1) the evolution Hamiltonian He is equal to the final Hamiltonian Hf. Before the evolution begins, the system is typically initialized in a ground state of the initial Hamiltonian Hi and the goal is to evolve the system in such a way that the system ends up in a ground state of the final Hamiltonian Hf at the end of the evolution. If the evolution is too fast, then the system can be excited to a higher energy state, such as the first excited state. In the present systems, methods, and apparatus, an “adiabatic” evolution is considered to be an evolution that satisfies the adiabatic condition:{dot over (s)}|1|dHe/ds|0|=δg2(s)where {dot over (s)} is the time derivative of s, g(s) is the difference in energy between the ground state and first excited state of the system (also referred to herein as the “gap size”) as a function of s, and δ is a coefficient much less than 1.
The evolution process in adiabatic quantum computing may sometimes be referred to as annealing. The rate that s changes, sometimes referred to as an evolution or annealing schedule, is normally slow enough that the system is always in the instantaneous ground state of the evolution Hamiltonian during the evolution, and transitions at anti-crossings (i.e., when the gap size is smallest) are avoided. Further details on adiabatic quantum computing systems, methods, and apparatus are described in U.S. Pat. No. 7,135,701.
Quantum Annealing
Quantum annealing is a computation method that may be used to find a low-energy state, typically preferably the ground state, of a system. Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend towards lower energy states because lower energy states are more stable. However, while classical annealing uses classical thermal fluctuations to guide a system to its global energy minimum, quantum annealing may use quantum effects, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly. It is known that the solution to a hard problem, such as a combinatorial optimization problem, may be encoded in the ground state of a system Hamiltonian and therefore quantum annealing may be used to find the solution to such hard problems. Adiabatic quantum computation is a special case of quantum annealing for which the system, ideally, begins and remains in its ground state throughout an adiabatic evolution. Thus, those of skill in the art will appreciate that quantum annealing systems and methods may generally be implemented on an adiabatic quantum computer, and vice versa. Throughout this specification and the appended claims, any reference to quantum annealing is intended to encompass adiabatic quantum computation unless the context requires otherwise.
Quantum annealing is an algorithm that uses quantum mechanics as a source of disorder during the annealing process. The optimization problem is encoded in a Hamiltonian HP, and the algorithm introduces strong quantum fluctuations by adding a disordering Hamiltonian HD that does not commute with HP. An example case is:HE=HP+ΓHD,
where Γ changes from a large value to substantially zero during the evolution and HE may be thought of as an evolution Hamiltonian similar to He described in the context of adiabatic quantum computation above. The disorder is slowly removed by removing HD (i.e., reducing Γ). Thus, quantum annealing is similar to adiabatic quantum computation in that the system starts with an initial Hamiltonian and evolves through an evolution Hamiltonian to a final “problem” Hamiltonian HP whose ground state encodes a solution to the problem. If the evolution is slow enough, the system will typically settle in a local minimum close to the exact solution; the slower the evolution, the better the solution that will be achieved. The performance of the computation may be assessed via the residual energy (distance from exact solution using the objective function) versus evolution time. The computation time is the time required to generate a residual energy below some acceptable threshold value. In quantum annealing, HP may encode an optimization problem and therefore HP may be diagonal in the subspace of the qubits that encode the solution, but the system does not necessarily stay in the ground state at all times. The energy landscape of HP may be crafted so that its global minimum is the answer to the problem to be solved, and low-lying local minima are good approximations.
The gradual reduction of Γ in quantum annealing may follow a defined schedule known as an annealing schedule. Unlike traditional forms of adiabatic quantum computation where the system begins and remains in its ground state throughout the evolution, in quantum annealing the system may not remain in its ground state throughout the entire annealing schedule. As such, quantum annealing may be implemented as a heuristic technique, where low-energy states with energy near that of the ground state may provide approximate solutions to the problem.